import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/9 9:54
 * @description 枚举第一行中的起点，然后以该起点查找最短路径，时间复杂度为 O(n^3) 由于 n最大为 10^2, 那么计算量为 10^6 < 10^7 能够AC
 */
public class Solution {
    public static void main(String[] args) {

    }
    int MAX = Integer.MAX_VALUE;
    public int minFallingPathSum(int[][] mat) {
        int n = mat.length;
        int ans = MAX;
        // 枚举首行的每个下标作为「起点」
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, find(mat, i));
        }
        return ans;
    }

    /**
     * 返回以 (0, u) 作为起点的最小路径和
     * @param mat 矩阵
     * @param u 起点
     * @return 值
     */
    int find(int[][] mat, int u) {
        int n = mat.length;
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) f[0][i] = i == u ? mat[0][i] : MAX;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j] = MAX;
                int val = mat[i][j];
                // 由正上方转移而来
                if (f[i-1][j] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j] + val);
                // 由左上方或右上方转移而来
                if (j - 1 >= 0 && f[i-1][j-1] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j-1] + val);
                if (j + 1 < n  && f[i-1][j+1] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j+1] + val);
            }
        }
        int ans = MAX;
        for (int i = 0; i < n; i++) ans = Math.min(ans, f[n-1][i]);
        return ans;
    }
}
